package com.peng.leetcode.bfs;

import java.util.LinkedList;
import java.util.Queue;

/**
 * HighestPeak
 * <p>
 * 1765. 地图中的最高点
 *
 * @author: lupeng6
 * @create: 2021/3/1 10:42
 */
public class HighestPeak {

    public static void main(String[] args) {

    }

    /**
     * 广度优先遍历
     *
     * @author lupeng6
     * @date 2021/3/1 10:42
     */
    public int[][] highestPeak(int[][] isWater) {
        int[][] operation = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int rows = isWater.length;
        int cols = isWater[0].length;

        int[][] visited = new int[rows][cols];

        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (isWater[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                }
            }
        }

        int[][] dist = new int[rows][cols];

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int x = poll[0];
            int y = poll[1];

            for (int[] opera : operation) {
                int newX = x + opera[0];
                int newY = y + opera[1];

                if (newX >= 0 && newX < rows
                        && newY >= 0 && newY < cols
                        && visited[newX][newY] == 0
                        && isWater[newX][newY] == 0) {
                    dist[newX][newY] = dist[x][y] + 1;
                    visited[newX][newY] = 1;
                    queue.offer(new int[]{newX, newY});
                }
            }
        }

        return dist;
    }
}
